The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Border Gateway Protocol (BGP) is an exterior gateway protocol (EGP) that is used to exchange routing information among network elements in the same or different autonomous systems. A network element is a device that is configured for managing, processing, and/or forwarding network traffic. (Examples of network elements include, but are not limited to, repeaters, bridges, switches, and routers.) A network element that executes one or more BGP processes is referred to herein as a BGP host or a BGP device. In order to exchange BGP routing information, two BGP hosts first establish with one another a transport protocol session such as, for example, a Transmission Control Protocol (TCP) session. The BGP hosts then establish a BGP peering session by exchanging, over the transport protocol session, a series of BGP OPEN messages that define the parameters of the BGP session. After the BGP session is open, the BGP hosts (performing as BGP peers) exchange all of their routing information. Thereafter, only updates or changes to the routing information are exchanged, or advertised, between the BGP hosts. The exchanged routing information is maintained by the BGP hosts during the existence of the BGP session.
The routing information exchanged during a BGP session includes routes to address destinations in one or more networks. A route comprises an address prefix of the destination (also referred to as prefix), and attributes that describe the path to the destination. At a BGP host, routes are stored in one or more Routing Information Bases (RIBs), where each BGP process executing on the BGP host typically manages its own RIB. In a typical BGP implementation, a BGP RIB may include three distinct portions: (a) Adj-RIBs-In, which stores routes received from BGP peers or learned from other protocols, (b) Loc-RIB, which stores routes that the BGP process has selected by applying its local policies to the routes stored in Adj-RIBs-In, and (c) Adj-RIBs-Out, which stores routes that the BGP process has selected for advertisement to its BGP peers. A BGP RIB may be implemented as a single physical routing table that includes each of the three portions as separate logical tables, as separate physical routing tables, or as some combination of one or more logical and/or physical routing tables.
The routes that a BGP host stores in a Adj-RIBs-In are typically received over a BGP session established with another BGP host. The routes stored in a Loc-RIB of the BGP host are selected from the routes in a Adj-RIBs-In by applying one or more route selection algorithms. The routes selected by the BGP host and stored in the Loc-RIB usually represent the best paths to the routes' respective address destinations. Once the best route to a certain address destination is selected and stored in the Loc-RIB, the BGP host advertises the route to its BGP peers by placing (or storing) the route in Adj-RIBs-Out.
Some or all of the best routes stored in a Loc-RIB are installed in a Forwarding Information Base (FIB) that is associated with the BGP process that manages that Loc-RIB. A FIB is a physical or logical table that stores routes used to forward network packets to the address destinations of the stored routes. A typical FIB stores only one route (the best route) for each address destination that is reachable through the network element that hosts the FIB. In a typical network element, a FIB is managed by a forwarding engine that is configured to receive network packets from other network elements and to forward these packets based on the routes installed in the FIB. A forwarding engine may comprise a set of hardware and/or software components capable of receiving and forwarding network traffic, and in different architectures the forwarding engine may be executing on a route processor or on a line card of a network element.
In a standard BGP implementation (such as, for example, a BGP implementation conforming to the BGP-4 standard defined in RFC1771 or to the MP-BGP standard defined in RCF2858), when the BGP session between two BGP hosts is closed or lost for whatever reason, each BGP host discards any routing information received from the other host and removes routes received from the other host from its RIBs and FIBs. Thus, when afterwards the two BGP hosts establish a new BGP session, in order to provide forwarding capabilities on each other's routes, the two BGP hosts need to go through the same time and resource consuming process of exchanging anew all of their routing information, running route selection algorithms, and installing the best routes in their respective FIBs.
In order to minimize the negative effects of such BGP restarts, a Graceful Restart mechanism for BGP has been proposed, the latest version of which was published by the IETF in December 2004 as draft-ietf-idr-restart-10.txt. The BGP Graceful Restart mechanism provides a new BGP capability, termed “Graceful Restart Capability”, which is advertised by a BGP host during the set up of a BGP session with another BGP host. A BGP host that advertises a Graceful Restart capability to its BGP peer guarantees that it is capable of preserving the forwarding state of routes associated with one or more identified address families and of forwarding packets on these routes while its BGP process is restarting. The BGP host that advertises a Graceful Restart capability is commonly referred to as the restarting BGP speaker; the BGP peer that has established a BGP session to a restarting BGP speaker is commonly referred to as the receiving BGP speaker. According to the BGP Graceful Restart mechanism, while the BGP process on the restarting BGP speaker is restarting the routes in its Loc-RIB are marked as “stale”; however, no routes are removed from the FIB and forwarding of network packets on “stale” routes is not affected. (As referred to herein, a “stale” route is a route that has been received from a BGP session that has since become unavailable.) When the receiving BGP speaker detects that the BGP session to the restarting BGP speaker has become unavailable, the receiving BGP speaker marks as stale the routes in its Loc-RIB that have previously been received from the restarting BGP speaker. The receiving BGP speaker, however, does not remove these routes from its FIB and the forwarding of network packets on these routes is not affected.
Network elements or devices built on certain hardware platforms may include multiple forwarding engines and may provide software or hardware failover mechanisms for switching from one forwarding engine to another. For example, some routers provide an active forwarding engine (with an active FIB) on a particular route processor or a line card, and a stand-by forwarding engine (with a stand-by FIB) on a different route processor or a line card. If a transport protocol session established at such router fails, the active forwarding engine automatically fails over to the stand-by forwarding engine. Typically, a forwarding engine failover requires re-installing the routes in the active FIB into the stand-by FIB before the failover is complete. On some network elements, the active FIB may be re-created at the stand-by forwarding engine by using special hardware or fast IPC mechanisms, and thus the forwarding engine failover at these network elements may be performed almost instantaneously.
However, on certain other network elements (such as the Cisco 10K Series router for example), it may take up to a few seconds to re-install the routes from the active FIB to the stand-by FIB. Network packets forwarded to such network elements during these transitional few seconds cannot be routed and must be dropped. Thus, an outage in the forwarding service provided by these network elements occurs. This problem is further exacerbated if a BGP process executing on such network element is configured to advertise to its BGP peers support for the BGP Graceful Restart capability. Such network element in effect advertises itself as a BGP host that provides the BGP Graceful Restart capability despite the fact that it physically cannot provide the BGP Graceful Restart guarantee of non-interrupted forwarding service during BGP restarts.
Based on the foregoing, there is a clear need for a technique that overcomes the above problem and provides for a non-interrupted forwarding service during BGP restarts.